#ifndef TRIETREE_H
#define TRIETREE_H

#include <unistd.h>
#include <stdint.h>
#include <vector>
#include <map>
#include <iostream>

class TrieTree {
public:
    void addNode(std::vector<uint32_t>& vWord) {
        if (vWord.empty()) return;

        TrieNode* pNode = &m_stRoot;
        for (auto& iWrod : vWord) {
            pNode = &(pNode->mNodes[iWrod]);
        }
        pNode->bTerminal = true;
    }
    bool find(uint32_t** pBegin, const uint32_t* pEnd, uint32_t& iLen) {
        if (nullptr == pBegin || *pBegin == nullptr || nullptr == pEnd || *pBegin >= pEnd) {
            return false;
        }

        bool bFind = false;
        const TrieNode* pNode = &m_stRoot;
        for (const uint32_t* p = pBegin; p < pEnd; ++p) {
            ++iLen;
            auto it = pNode->mNodes.find(*p);
            if (it == pNode->mNodes.end() && pNode->pFail == &m_stRoot) {
                break;
            }
            if ()

            pNode = &it->second;
            if (pNode->bTerminal) {
                bFind = true;
                iLen = p - pBegin + 1;
            }
        }

        return bFind;
    }
    void constructFailNodes() {
        std::vector<TrieNode*> vNodePtrs;
        m_stRoot.addFailNode(m_stRoot, vNodePtrs);
    }

private:
    struct TrieNode {
        bool bTerminal = false;
        std::map<uint32_t, TrieNode> mNodes;
        TrieNode* pFail = nullptr;

        void addFailNode(TrieNode& stRoot, std::vector<TrieNode*>& vNodes) {
            for (auto& [iChar, stNode] : mNodes) {
                TrieNode* pTarget = pFail;
                while (pTarget) {
                    auto it = pTarget->mNodes.find(iChar);
                    if (it != pTarget->mNodes.end()) {
                        stNode.pFail = &(it->second);
                        break;
                    }
                    pTarget = pTarget->pFail;
                }
                if (pTarget == nullptr)
                    stNode.pFail = &stRoot;

                vNodes.emplace_back(&stNode);
            }

            if (!vNodes.empty()) {
                TrieNode* pTarget = *(vNodes.begin());
                vNodes.erase(vNodes.begin());
                pTarget->addFailNode(stRoot, vNodes);
            }
        }
    };

    TrieNode m_stRoot;
};

#endif // TRIETREE_H
